// class Solution
// {
// public:
//     string minWindow(string s, string t)
//     {
//         int ans = INT_MAX, ans_left = 0;
//         char hash_target[100] = {0};
//         char hash_s[100] = {0};
//         for (auto e : t)
//             hash_target[e - 'A']++;
//         int sz = t.size(); // sz表示有效字符的总个数
//         int valid_size = 0;
//         for (int left = 0, right = 0; right < s.size(); ++right)
//         {
//             char t = s[right];
//             hash_s[t - 'A']++; // 进窗口
//             // 判断是不是有效字符
//             if (hash_target[t - 'A'] != 0)
//             {
//                 if (hash_s[t - 'A'] <= hash_target[t - 'A'])
//                     ++valid_size;
//             }
//             // 接下来不断的出窗口，直到valid_size等于2
//             while (valid_size >= sz)
//             {
//                 int left_tag = s[left] - 'A';
//                 // cout << s[left] << ' ' << left_tag << endl;
//                 if (hash_target[left_tag] != 0 && hash_s[left_tag] <= hash_target[left_tag])
//                 {
//                     if (valid_size == sz && right - left + 1 < ans)
//                     {
//                         ans_left = left;
//                         ans = right - left + 1;
//                     }
//                     --valid_size;
//                 }
//                 hash_s[s[left++] - 'A']--;
//             }
//             if (ans == sz)
//                 break;
//         }
//         if (ans == INT_MAX)
//             return "";
//         else
//             return s.substr(ans_left, ans);
//     }
// };
#include <iostream>
#include <string>
using namespace std;

class Solution
{
public:
    string minWindow(string s, string t)
    {
        int ans = INT_MAX, ans_left = 0;
        char hash_target[100] = {0};
        char hash_s[100] = {0};
        int sz = 0;
        for (auto e : t)
        {
            hash_target[e - 'A']++;
            if (hash_target[e - 'A'] == 1)
                sz++;
        } // sz表示有效字符的总种类
        int valid_size = 0;
        for (int left = 0, right = 0; right < s.size(); ++right)
        {
            char t = s[right];
            hash_s[t - 'A']++; // 进窗口
            // 判断是不是有效字符
            if (hash_s[t - 'A'] == hash_target[t - 'A'])
                ++valid_size;
            // 接下来不断的出窗口，直到valid_size等于sz
            while (valid_size == sz)
            {
                int left_tag = s[left] - 'A';
                // cout << s[left] << ' ' << left_tag << endl;
                if (hash_s[left_tag] == hash_target[left_tag])
                {
                    if (right - left + 1 <= ans)
                    {
                        ans_left = left;
                        ans = right - left + 1;
                    }
                    --valid_size;
                }
                hash_s[s[left++] - 'A']--;
            }
            if (ans == sz)
                break;
        }
        if (ans == INT_MAX)
            return "";
        else
            return s.substr(ans_left, ans);
    }
};